package com.leetcode.algorithm.y22.m06;

/**
 * 516. 最长回文子序列
 * 
 * https://leetcode.cn/problems/longest-palindromic-subsequence/
 * 
 * @author jie.deng
 *
 */
class Question0516Solution01 {

	public int longestPalindromeSubseq(String s) {
		int len = s.length();

		// DP状态定义
		// dp[i][j]表示 s[i...j]最长回文子序列的长度
		int[][] dp = new int[len][len];
		// DP状态初始化

		// 状态转移方程：
		for (int i = len - 1; i >= 0; i--) { // 注意计算方向，从左下到右上
			dp[i][i] = 1;// 单字符
			for (int j = i + 1; j < len; j++) {
				if (s.charAt(i) == s.charAt(j)) {
					if (j - i == 1) {
						dp[i][j] = 2;
					} else {
						dp[i][j] = dp[i + 1][j - 1] + 2;// 注意计算方向，从左下到右上，才能保证 dp[i + 1][j - 1] 先于 dp[i][j] 赋值
					}
				} else {
					dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
				}
			}
		}

		return dp[0][len - 1];
	}

}